package com.sun.alen.stageone;

/**
 * 斐波那契数列计算类
 * 包含递归和递推两种方式计算斐波那契数列
 */
public class Fibonacci {
    /**
     * 主函数，用于测试斐波那契数列的两种计算方式
     * 分别调用递归和递推方法计算第40位斐波那契数，并输出结果和执行时间
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        long begin1 = System.currentTimeMillis();
        System.out.println("递归结果"+fib(40));
        long end1 = System.currentTimeMillis();
        System.out.println("递推时间"+(end1-begin1));
        long begin2 = System.currentTimeMillis();
        System.out.println("递推结果"+fib2(40));
        long end2 = System.currentTimeMillis();
        System.out.println("递推时间"+(end2-begin2));
    }

    /**
     * 使用递归方式计算斐波那契数列第n位的值
     * 斐波那契数列定义：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n>=2)
     * @param n 要计算的位置，从0开始
     * @return 斐波那契数列第n位的值
     */
    public static int fib(int n){
        if(n<=0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        // 递归计算前两项之和
        return fib(n-1)+fib(n-2);
    }

    /**
     * 使用递推方式计算斐波那契数列第n位的值
     * 通过循环迭代的方式避免递归的重复计算，提高效率
     * @param n 要计算的位置，从0开始
     * @return 斐波那契数列第n位的值
     */
    public static int fib2(int n){
        if(n<=0){
            return 0;
        }
        // 初始化前两项的值
        int a = 0;
        int b = 1;
        int c = 1;
        // 从第2位开始迭代计算到第n位
        for(int i=2;i<=n;i++){
            c = a+b;
            a = b;
            b = c;
        }
        return c;
    }
}

